package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Vector;

import cern.colt.matrix.impl.SparseDoubleMatrix2D;

import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * A class of solvers that produce more snowflakes than necessary and then pick some of them as a
 * solution.
 * 
 * @author chato
 * 
 */
public abstract class ProduceAndChooseSolver extends Solver {

	public enum RankingStrategy {
		/**
		 * Sort in decreasing order by intra similarity, then pick the top elements.
		 */
		RANK_BY_INTRA,

		/**
		 * Apply a greedy heuristic to add the element that increases the most ( gamma * intra + ( 1
		 * - gamma ) * inter )
		 */
		RANK_BY_INTRA_INTER,

		/**
		 * Apply a densest-subgraph heuristic.
		 */
		RANK_BY_DENSEST_SUBGRAPH;

		public static RankingStrategy getDefault() {
			return RANK_BY_INTRA;
		}
	}

	RankingStrategy rankingStrategy;

	/**
	 * To be used with {@link RankingStrategy#RANK_BY_INTRA_INTER}
	 */
	double interSimilarityWeight = -1.0;

	ProduceAndChooseSolver(ProblemInstance problem) {
		super(problem);
		setRankingStrategy(RankingStrategy.getDefault());
	}

	public void setRankingStrategy(RankingStrategy strategy) {
		this.rankingStrategy = strategy;
	}

	public RankingStrategy getRankingStrategy() {
		return this.rankingStrategy;
	}

	public void setInterSimilarityWeight(double interSimilarityWeight) {
		if (rankingStrategy == RankingStrategy.RANK_BY_INTRA_INTER || rankingStrategy == RankingStrategy.RANK_BY_DENSEST_SUBGRAPH) {
			this.interSimilarityWeight = interSimilarityWeight;
		} else {
			throw new IllegalArgumentException("This ranking strategy does not need an inter-similarity weight");
		}
	}

	@Override
	final public Vector<Snowflake> solve(int numRequested) {
		
		Vector<Snowflake> produced = produceManySnowflakes(numToProduce(numRequested));
		
		return getTopSolutionByRankingStrategy(produced, numRequested);
	}
	
	final public Vector<Snowflake> getTopSolutionByRankingStrategy(Vector<Snowflake> produced, int numRequested ) {
		switch (rankingStrategy) {
		case RANK_BY_INTRA:
			return getTopSolutionsByIntra(produced, numRequested);
		case RANK_BY_INTRA_INTER:
			if (interSimilarityWeight < 0.0) {
				throw new IllegalArgumentException("This ranking strategy requires an inter similarity weight");
			}
			return getTopSolutionsByInterIntra(produced, numRequested);
		case RANK_BY_DENSEST_SUBGRAPH:
			if (interSimilarityWeight < 0.0) {
				throw new IllegalArgumentException("This ranking strategy requires an inter similarity weight");
			}
			return getTopSolutionsByDensestSubgraph(produced, numRequested);
		default:
			throw new IllegalStateException("Unknown ranking strategy");
		}
	}
	
	abstract public int numToProduce(int numRequested);

	private Vector<Snowflake> getTopSolutionsByIntra(Vector<Snowflake> produced, int numRequested) {
		Snowflake[] allSortedSolutions = produced.toArray(new Snowflake[] {});
		Snowflake.sortByDecreasingSumCompat(allSortedSolutions);
		Vector<Snowflake> selected = new Vector<Snowflake>(numRequested);
		for (int i = 0; i < numRequested && i < allSortedSolutions.length; i++) {
			selected.add(allSortedSolutions[i]);
		}
		return selected;
	}

	private Vector<Snowflake> getTopSolutionsByInterIntra(Vector<Snowflake> produced, int numRequested) {
		if (interSimilarityWeight < 0.0) {
			throw new IllegalStateException("You need to set the value of 'inter similarity weight'");
		}

		// Sort in decreasing order of sum intra
		Snowflake[] allSortedSolutions = produced.toArray(new Snowflake[] {});
		Snowflake.sortByDecreasingSumCompat(allSortedSolutions);

		Vector<Snowflake> available = new Vector<Snowflake>();
		for (Snowflake solution : allSortedSolutions) {
			available.add(solution);
		}
		Vector<Snowflake> selected = new Vector<Snowflake>(numRequested);
		double currentSumIntra = 0.0;
		double currentSumOneMinusInter = 0.0;
		while (selected.size() < numRequested && selected.size() < produced.size()) {

			double maxScore = Double.NEGATIVE_INFINITY;
			int bestCandidateId = -1;

			if (available.size() == 0) {
				throw new IllegalStateException("There are no available candidates");
			}

			for (int candidateId = 0; candidateId < available.size(); candidateId++) {
				Snowflake candidate = available.get(candidateId);
				double score = scoreSetIntraInter(selected, candidate, currentSumIntra, currentSumOneMinusInter);
				if (score > maxScore) {
					bestCandidateId = candidateId;
					maxScore = score;
				}
			}

			if (bestCandidateId == -1) {
				throw new IllegalStateException("There is no best candidate (available.size()==" + available.size() + ", maxScore==" + maxScore + ")");
			}

			// Compute new scores
			Snowflake bestCandidate = available.get(bestCandidateId);
			currentSumIntra += bestCandidate.getSumIntraCompat();
			for (Snowflake snowflake : selected) {
				currentSumOneMinusInter += 1.0 - problem.maxPairwiseCompatibility(snowflake, bestCandidate);
			}

			// Add element to solution
			available.remove(bestCandidateId);
			selected.add(bestCandidate);

		}
		return selected;
	}

	/**
	 * Score a set of snowflakes composed of all the elements in 'selected' plus the element
	 * 'candidate'.
	 * 
	 * The score is {@link #interSimilarityWeight} * sum(inter) + ( 1 -
	 * {@link #interSimilarityWeight}) * sum(intra)
	 * 
	 * Used by {@link #getTopSolutionsByInterIntra(Vector, int)}.
	 * 
	 * @param selected the snowflakes selected so far
	 * @param candidate the new snowflake to add
	 * @param selectedSumIntra the sum of {@link Snowflake#getSumIntraCompat()} for elements in
	 *            selected
	 * @return the score of the union
	 */
	private double scoreSetIntraInter(Vector<Snowflake> selected, Snowflake candidate, double selectedSumIntra, double selectedSumOneMinusInter) {
		double sumIntra = selectedSumIntra + candidate.getSumIntraCompat();
		double sumOneMinusInter = selectedSumOneMinusInter;
		for (Snowflake snowflake : selected) {
			sumOneMinusInter += 1.0 - problem.maxPairwiseCompatibility(snowflake, candidate);
		}
		// Experiments 20110222 were run with this wrong formula:
		// return (interSimilarityWeight * sumInter) + ((1.0 - interSimilarityWeight) * sumIntra);
		// Experiments 20110325 used this formula, which differs by an additive factor from the
		// current one:
		// return ((1.0 - interSimilarityWeight) * sumIntra) - (interSimilarityWeight * sumInter);
		return ((1.0 - interSimilarityWeight) * sumIntra) + (interSimilarityWeight * sumOneMinusInter);
	}

	/**
	 * 
	 * Applies a heuristic to find a densest subgraph.
	 * 
	 * The weights in the subgraph are a function of inter similarity and intra similarity.
	 * 
	 * Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama. Greedily finding a dense subgraph. Journal
	 * of Algorithms, 34(2):203 – 221, 2000.
	 * 
	 * @param produced
	 * @param numRequested
	 * @return
	 */
	private Vector<Snowflake> getTopSolutionsByDensestSubgraph(Vector<Snowflake> produced, int numRequested) {
		
		int numProduced = produced.size();
		SparseDoubleMatrix2D w = new SparseDoubleMatrix2D(numProduced, numProduced);
		double gamma = 1.0 - interSimilarityWeight;

		// Construct matrix w
		for (int ui = 0; ui < numProduced; ui++) {
			Snowflake u = produced.get(ui);
			for (int vi = 0; vi < numProduced; vi++) {
				Snowflake v = produced.get(vi);
				double value = ((gamma / (2.0 * ((double) numRequested - 1.0))) * (u.getSumIntraCompat() + v.getSumIntraCompat()))
						+ ((1.0 - gamma) * (1.0 - problem.maxPairwiseCompatibility(u, v)));
				w.setQuick(ui, vi, value);
			}
		}

		// Add all to selected
		IntOpenHashSet selected = new IntOpenHashSet(produced.size());
		for (int ui = 0; ui < produced.size(); ui++) {
			selected.add(ui);
		}

		// Remove until condition is met
		while (selected.size() > numRequested) {
			double minWeightedDegree = Double.POSITIVE_INFINITY;
			int minElement = -1;
			for (int ui : selected) {
				double weightedDegree = 0.0;
				for (int vi : selected) {
					weightedDegree += w.getQuick(ui, vi);
					if (weightedDegree > minWeightedDegree) { // early exit
						break;
					}
				}
				if (weightedDegree < minWeightedDegree) {
					minWeightedDegree = weightedDegree;
					minElement = ui;
				}
			}
			if (!selected.contains(minElement)) {
				throw new IllegalStateException("Tried to remove element " + minElement + " that does not belong to " + selected);
			}
			selected.remove(minElement);
		}

		// Build the solution
		Vector<Snowflake> solution = new Vector<Snowflake>(numRequested);
		for (int ui : selected) {
			Snowflake u = produced.get(ui);
			solution.add(u);
		}
		return solution;
	}

	/**
	 * Generate a number of snowflakes
	 * 
	 * @param numSnowflakes the minimum number of snowflakes to produce
	 * @return a set of snowflakes, possibly larger than the number of requested elements
	 */
	abstract Vector<Snowflake> produceManySnowflakes(int numSnowflakes);
}
